package DataStructure;

import java.util.Arrays;

/**
 * @author ligaojian
 * @version 1.0
 * @description: 哈希表的实现
 * @date 2021/11/8 10:23
 */
public class HashTable {
    int[] elem;
    public int count = 0;
    public int size = 12;
    public final int NULLKEY = Integer.MIN_VALUE;

    //构造函数，初始化哈希表
    public HashTable() {
        this.elem = new int[size];
//        for (int i = 0; i < elem.length; i++) {
//            elem[i] = NULLKEY;
//        }
        Arrays.fill(elem, NULLKEY);  //快速赋初值
    }

    public void insert (int key) {
        //1.判断是否需要插入？ 元素插入完成
        if (count ==size) {
            return;
        }
        //计算hash地址
        int index = key % size;

        //判断该地址是否为NULLKEY
        //判断是否存在hash冲突
        while (this.elem[index] !=NULLKEY) {
            //使用线性探测解决冲突
            index = (index+1) % size;
        }
        //插入，赋值。
        this.elem[index] = key;  //向index这个位置插入元素
        count++;
    }

    public String search(int key) {
        //计算hash地址
        int index = key % size;
        //判断该地址值和key是否相等
        while (this.elem[index] !=key) {
            index = (index+1) % size;

            //如果找不到，有两种情况，1是改地址为初始值，未赋值。2.线性探测遍历一遍回到原来位置
            if (this.elem[index] == NULLKEY || index == key %size) {
                return key+"不存在";
            }
        }
        return "存在，索引为："+index;
    }
}
